package week_05.sort;

public class MergeSort implements Sort {
    @Override
    public String toString() {
        return "MergeSort:";
    }

    @Override
    public void sort(int[] nums) {
        mergerSort(nums, 0, nums.length - 1);
    }

    public void mergerSort(int[] nums, int l, int r) {
        // 分治排序 外部无序 内部有序 每次排现在的2分之一
        if (l >= r) return;
        int mid = (l + r) / 2;
        mergerSort(nums, l, mid);
        mergerSort(nums, mid + 1, r);
        // 合并两段
        merge(nums, l, mid, r);
    }

    public void merge(int[] nums, int l, int mid, int r) {
        int p = l;
        int q = mid + 1;
        int[] tmp = new int[r - l + 1];
        for (int k = 0; k < tmp.length; k++) {
            // 当 右边已经处理完：q>r
            // 或者 左边没处理完 p<=mid 且左边小于等于右边
            if (q > r || (p <= mid && nums[p] <= nums[q])) {
                tmp[k] = nums[p];
                p++;
            } else {
                tmp[k] = nums[q];
                q++;
            }
        }
//        while (p <= mid || q <= r) {
//            int cur = p + q - l - mid - 1;
//            if (q > r || (p <= mid && nums[p] <= nums[q])) {
//                tmp[cur] = nums[p];
//                p++;
//            } else {
//                tmp[cur] = nums[q];
//                q++;
//            }
//        }
        // 把新排好的数组部分填装回去
        for (int i = 0; i < tmp.length; i++) {
            nums[l + i] = tmp[i];
        }
    }

}
